#include <iostream>
#include <math.h>
#include <vector>
#include "Point.h"

using namespace std;

struct Cluster {
	int id;
	int level;
	int leftId;
	int rightId;
	double value;
};

void findSimpleLinkageMinIndex(vector < vector<double> > inputMatrix, int size, double& value, int& indexL, int& indexC )
{
	value = 10000; // initialize

	for(int i = 0; i < size; i++)
	{
		vector<double> vLine = inputMatrix.at(i);
		for (int j = i+1; j < size; j++)
		{
			if((value >= vLine[j]) && (vLine[j] > 0))
			{
				value = vLine[j];
				indexL = i;
				indexC = j;
			}
		}
	}
}

void findCompleteLinkageMaxIndex(vector < vector<double> > inputMatrix, int size, double& value, int& indexL, int& indexC )
{
	value = 0; // initialize

	for(int i = 0; i < size; i++)
	{
		vector<double> vLine = inputMatrix.at(i);
		for (int j = i+1; j < size; j++)
		{
			if((value <= vLine[j]) && (vLine[j] > 0))
			{
				value = vLine[j];
				indexL = i;
				indexC = j;
			}
		}
	}
}

void updateSimpleLinkageInputMatrix(vector < vector<double> >& inputMatrix, int size, int indexL, int indexC)
{
	vector < vector<double> > tmpMatrix;
	for(int i = 0; i < size; i++)
	{
		if((i != indexL) && (i != indexC)) {
			vector<double> vLine = inputMatrix.at(i);
			vector<double> vLineTmp;
			for (int j = 0; j < size; j++)
			{
				if((j != indexL) && (j != indexC))
				{
					vLineTmp.push_back(vLine[j]);
				}
			}
			double v1 = vLine[indexL];
			cout << "v1 #" << i << " :" << v1 << endl;
			double v2 = vLine[indexC];
			cout << "v2 #" << i << " :" << v2 << endl;
			double minValue = v1 < v2 ? v1 : v2;
			cout << "minValue #" << i << " :" << minValue << endl;
			vLineTmp.push_back(minValue);

			for (int c = 0; c < vLineTmp.size(); c++) {
				cout << vLineTmp.at(c) << " ";
			}
			cout << endl;
			cout << "----------------------------------------------" << endl;
			tmpMatrix.push_back(vLineTmp);
		}
	}
	vector<double> vLine1 = inputMatrix.at(indexL);
	vector<double> vLine2 = inputMatrix.at(indexC);
	vector<double> vLineTmp;
	for (int j = 0; j < size; j++)
	{
		if((j != indexL) && (j != indexC))
		{
			double v1 = vLine1[j];
			double v2 = vLine2[j];
			double minValue = v1 < v2 ? v1 : v2;
			vLineTmp.push_back(minValue);
		}
	}
	vLineTmp.push_back(0); //zero no final
	for (int c = 0; c < vLineTmp.size(); c++) {
		cout << vLineTmp.at(c) << " ";
	}
	cout << endl;
	cout << "----------------------------------------------" << endl;

	tmpMatrix.push_back(vLineTmp);

	inputMatrix = tmpMatrix;
}

void updateCompleteLinkageInputMatrix(vector < vector<double> >& inputMatrix, int size, int indexL, int indexC)
{
	vector < vector<double> > tmpMatrix;
	for(int i = 0; i < size; i++)
	{
		if((i != indexL) && (i != indexC)) {
			vector<double> vLine = inputMatrix.at(i);
			vector<double> vLineTmp;
			for (int j = 0; j < size; j++)
			{
				if((j != indexL) && (j != indexC))
				{
					vLineTmp.push_back(vLine[j]);
				}
			}
			double v1 = vLine[indexL];
			cout << "v1 #" << i << " :" << v1 << endl;
			double v2 = vLine[indexC];
			cout << "v2 #" << i << " :" << v2 << endl;
			double maxValue = v1 > v2 ? v1 : v2;
			cout << "maxValue #" << i << " :" << maxValue << endl;
			vLineTmp.push_back(maxValue);

			for (int c = 0; c < vLineTmp.size(); c++) {
				cout << vLineTmp.at(c) << " ";
			}
			cout << endl;
			cout << "----------------------------------------------" << endl;
			tmpMatrix.push_back(vLineTmp);
		}
	}
	vector<double> vLine1 = inputMatrix.at(indexL);
	vector<double> vLine2 = inputMatrix.at(indexC);
	vector<double> vLineTmp;
	for (int j = 0; j < size; j++)
	{
		if((j != indexL) && (j != indexC))
		{
			double v1 = vLine1[j];
			double v2 = vLine2[j];
			double maxValue = v1 > v2 ? v1 : v2;
			vLineTmp.push_back(maxValue);
		}
	}
	vLineTmp.push_back(0); //zero no final
	for (int c = 0; c < vLineTmp.size(); c++) {
		cout << vLineTmp.at(c) << " ";
	}
	cout << endl;
	cout << "----------------------------------------------" << endl;

	tmpMatrix.push_back(vLineTmp);

	inputMatrix = tmpMatrix;
}

void findIndexValue(vector < vector<double> > inputMatrix, int size, double value, int& leftId, int& rightId )
{
	for(int i = 0; i < size; i++)
	{
		vector<double> vLine = inputMatrix.at(i);
		for (int j = i+1; j < size; j++)
		{
			if((value == vLine[j]) && (vLine[j] > 0))
			{
				leftId = i;
				rightId = j;
				break;
			}
		}
	}
}

int main( int argc, char** argv )
{
	const int k = 6;

	vector < vector<double> > inputMatrix;
	vector < vector<double> > tmp;

	double l1[k] = {0, 662, 877, 255, 412, 996};
	//double l1[k] = {0, 0.71, 5.66, 3.61, 4.24, 3.20};
	//double l1[k] = {0, 0.999457, 0.994384, 0.997441, 0.998272, 0.997563};
	vector<double> v1;
	for (int i=0; i<k; i++){
		v1.push_back(l1[i]);
	}
	inputMatrix.push_back(v1);

	double l2[k] = {662, 0, 295, 468, 268, 400};
	//double l2[k] = {0.71, 0, 4.95, 2.92, 3.54, 2.5};
	//double l2[k] = {0.999457, 0, 0.995707, 0.99816, 0.999173, 0.998874};
	vector<double> v2;
	for (int i=0; i<k; i++){
		v2.push_back(l2[i]);
	}
	inputMatrix.push_back(v2);

	double l3[k] = {877, 295, 0, 754, 564,138};
	//double l3[k] = {5.66, 4.95, 0, 2.24, 1.41, 2.5};
	//double l3[k] = {0.994384, 0.995707,	0, 0.998824, 0.997113, 0.997521};
	vector<double> v3;
	for (int i=0; i<k; i++){
		v3.push_back(l3[i]);
	}
	inputMatrix.push_back(v3);

	double l4[k] = {255, 468, 754, 0, 219, 869};
	//double l4[k] = {3.61, 2.92, 2.24, 0, 1.0, 0.5};
	//double l4[k] = {0.997441, 0.99816, 0.998824, 0, 0.997913, 0.997879};
	vector<double> v4;
	for (int i=0; i<k; i++){
		v4.push_back(l4[i]);
	}
	inputMatrix.push_back(v4);

	double l5[k] = {412, 268, 564, 219, 0, 669};
	//double l5[k] = {4.24, 3.54, 1.41, 1.0, 0, 1.12};
	//double l5[k] = {0.998272, 0.999173, 0.997113, 0.997913, 0, 0.999877};
	vector<double> v5;
	for (int i=0; i<k; i++){
		v5.push_back(l5[i]);
	}
	inputMatrix.push_back(v5);

	double l6[k] = {996, 400, 138, 869, 669, 0};
	//double l6[k] = {3.2, 2.5, 2.5, 0.5, 1.12, 0};
	//double l6[k] = {0.997563, 0.998874, 0.997521, 0.997879, 0.999877, 0};
	vector<double> v6;
	for (int i=0; i<k; i++){
		v6.push_back(l6[i]);
	}
	inputMatrix.push_back(v6);

	cout << "----------------------------------------------" << endl;
	cout << "Input Matrix" << endl;
	cout << "----------------------------------------------" << endl;

	for (int l = 0; l < k; l++) {
		vector<double> vLine = inputMatrix.at(l);
		for (int c = 0; c < k; c++) {
			cout << vLine.at(c) << " ";
		}
		cout << endl;
	}

	vector<Cluster> vCluster;
	int id = k+1;

	tmp = inputMatrix;
	double level[k-1];
	//level[0] = 0;
	double m = 0;
	double size = k;

	/*
	 * Type:
	 * -----
	 * 0, Simple Linkage
	 * 1, Complete Linkage
	 * 2, Average linkage
	 * 3, Average group linkage
	 * */
	int type = 0;

	for (int it = 0; it < k-1; it++) {
		cout << "----------------------------------------------" << endl;
		cout << "Iteration #" << (it+1) << endl;
		cout << "----------------------------------------------" << endl;

		int leftId = -1;
		int rightId = -1;
		int indexL = -1;
		int indexC = -1;
		double value = -1;

		switch (type)
		{
			case 0:
				findSimpleLinkageMinIndex(tmp, size, value, indexL, indexC);
				cout << "MinIndex #" << (it+1) << " : value(" << value << ") l(" << indexL << ") c(" << indexC << ")" << endl;
				cout << "----------------------------------------------" << endl;

//				findIdValue(inputMatrix, k, value, leftId, rightId );
//				cout << "OrigianlIndex #" << (it+1) << " : value(" << value << ") l(" << leftId << ") r(" << rightId << ")" << endl;
//				cout << "----------------------------------------------" << endl;

				updateSimpleLinkageInputMatrix(tmp, size, indexL, indexC);

			break;

			case 1:
				findCompleteLinkageMaxIndex(tmp, size, value, indexL, indexC);
				cout << "MaxIndex #" << (it+1) << " : value(" << value << ") l(" << indexL << ") c(" << indexC << ")" << endl;
				cout << "----------------------------------------------" << endl;

//				findIdValue(inputMatrix, k, value, leftId, rightId );
//				cout << "OrigianlIndex #" << (it+1) << " : value(" << value << ") l(" << leftId << ") r(" << rightId << ")" << endl;
//				cout << "----------------------------------------------" << endl;

				updateCompleteLinkageInputMatrix(tmp, size, indexL, indexC);

			break;
		}

		//Update global variables
		m++;
		level[(it)] = value;
		size--;

		//New input matrix
		cout << "New Input Matrix #" << (it+1) << " : " << endl;
		for (int l = 0; l < size; l++) {
			vector<double> vLine = tmp.at(l);
			for (int c = 0; c < size; c++) {
				cout << vLine.at(c) << " ";
			}
			cout << endl;
		}

		//Save Cluster
//		Cluster c;
//		c.id = k++;
//		c.level = m;
//		c.leftId = originalIndexL;
//		c.rightId = originalIndexR;

//		vCluster.push_back(c);
	}

	cout << "----------------------------------------------" << endl;
	cout << "Input Matrix" << endl;
	cout << "----------------------------------------------" << endl;

	for (int l = 0; l < k; l++) {
		vector<double> vLine = inputMatrix.at(l);
		for (int c = 0; c < k; c++) {
			cout << vLine.at(c) << " ";
		}
		cout << endl;
	}

	cout << endl;
	cout << "----------------------------------------------" << endl;
	for (int i = 0; i < k-1; i++) {
		cout << "Level #" << i+1 << ": ";
		int indexL = -1;
		int indexC = -1;
		cout << level[i] << endl;
		findIndexValue(inputMatrix, k, level[i], indexL, indexC);
		cout << "Merged: A" << (indexL+1) << (indexC+1) << endl;
		cout << "----------------------------------------------" << endl;
	}

	return 0;

}

